package leetCode;

public class Q53 {
    public int maxSubArray(int[] nums) {
        int len = nums.length;

        //以i结束的和为dp[i]
        int[] dp = new int[len];
        dp[0] = nums[0];

        for(int i = 1;i<len;i++){
            if(dp[i-1]<0) dp[i] = nums[i];

            else dp[i] = dp[i-1]+nums[i];
        }

        int res = dp[0];
        for(int i=1;i<len;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Q53().maxSubArray(new int[]{-2, -1}));
    }
}
